# -*- coding: utf-8 -*-

"""剑指 Offer II 082. 含有重复元素集合的组合
给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。 

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30"""


from collections import Counter
from copy import deepcopy


class Solution:
    """回溯+递归
    剪枝：
    1. 剩余的即使全选也达不到 target 停止
    2. total > target, 停止
    3. 元素全部决策完 停止
    4. total = target, 收集结果，停止
    
    经计算，结果有重复如[1,7], [7,1]为重复
    排序，还有[1,7], [1,7]的问题
    计数排序，只保留[1,7]；
    要求两点：序列，计数"""
    def combinationSum2(self, candidates, target):
        pool = [[n, count] for n, count in Counter(candidates).items()]
        answer, hi = [], len(candidates)
        def fork(pool, i, group, total):
            if total+sum([n*count for n, count in pool[i:]]) < target:
                return
            if total > target:
                return
            if total == target:
                answer.append(group)
                return
            if i == hi:
                return

            if pool[i][1]:
                group_new = group.copy()
                pool_new = deepcopy(pool)
                pool_new[i][1] -= 1
                group_new.append(pool_new[i][0])
                fork(pool_new, i, group_new, total+pool_new[i][0])
                fork(pool, i+1, group, total)
            else:
                fork(pool, i+1, group, total)
                
        fork(pool, 0, [], 0)
        return answer


if __name__ == '__main__':
    so = Solution()
    print(so.combinationSum2(candidates = [10,1,2,7,6,1,5], target = 8))
    print(so.combinationSum2(candidates = [2,5,2,1,2], target = 5))
